import java.util.Arrays;

/**
 * @author ghp
 * @title
 * @description
 */
public class Solution {

    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        if ((sum & 1) == 1) {
            // 如果和是奇数，必定不能对半分，直接返回false（位运算比取模要快）
            return false;
        }
        // 对半分的容量
        int mid = sum / 2;
        // 创建dp数组，dp[i]表示背包容量为j时，能否从nums的[0,i]区间中寻找能够填充j的元素（false-不能，true-能）
        boolean[] dp = new boolean[mid + 1];
        dp[0] = true;
        // 遍历行，也就是物品的个数
        for (int i = 0; i < n; i++) {
            // 遍历列，也就是背包的容量
            for (int j = mid; j >= nums[i]; j--) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[mid];
    }
}